Dive into Algorithms by Bradford Tuckfield
Author:Bradford Tuckfield [Tuckfield, Bradford]
Language: eng
Format: epub, mobi
ISBN: 9781718500693
Published: 2020-11-17T00:00:00+00:00
Implementing Nearest Neighbor Search
Weâll start by writing a function that can find the nearest neighbor of any given city. Suppose that we have a point called point and a list of cities called cities. The distance between point and the jth element of cities is given by the following Pythagorean-style formula:
point = [0.5,0.5] j = 10 distance = math.sqrt((point[0] - cities[j][0])**2 + (point[1] - cities[j][1])**2)
If we want to find which element of cities is closest to our point (the pointâs nearest neighbor), we need to iterate over every element of cities and check the distance between the point and every city, as in Listing 6-1.
def findnearest(cities,idx,nnitinerary): point = cities[idx] mindistance = float('inf') minidx = - 1 for j in range(0,len(cities)): distance = math.sqrt((point[0] - cities[j][0])**2 + (point[1] - cities[j][1])**2) if distance < mindistance and distance > 0 and j not in nnitinerary: mindistance = distance minidx = j return(minidx)
Listing 6-1: The findnearest() function, which finds the nearest city to a given city
After we have this findnearest() function, weâre ready to implement the nearest neighbor algorithm. Our goal is to create an itinerary called nnitinerary. Weâll start by saying that the first city in cities is where our salesman starts:
nnitinerary = [0]
If our itinerary needs to have N cities, our goal is to iterate over all the numbers between 0 and N â 1, find for each of those numbers the nearest neighbor to the most recent city we visited, and append that city to our itinerary. Weâll accomplish that with the function in Listing 6-2, donn() (short for âdo nearest neighborâ). It starts with the first city in cities, and at every step adds the closest city to the most recently added city until every city has been added to the itinerary.
def donn(cities,N): nnitinerary = [0] for j in range(0,N - 1): next = findnearest(cities,nnitinerary[len(nnitinerary) - 1],nnitinerary) nnitinerary.append(next) return(nnitinerary)
Listing 6-2: A function that successively finds the nearest neighbor to each city and returns a complete itinerary
We already have everything we need to check the performance of the nearest neighbor algorithm. First, we can plot the nearest neighbor itinerary:
plotitinerary(cities,donn(cities,N),'TSP - Nearest Neighbor','figure3')
Figure 6-3 shows the result we get.
Figure 6-3: The itinerary generated by the nearest neighbor algorithm
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Coding Theory | Localization |
Logic | Object-Oriented Design |
Performance Optimization | Quality Control |
Reengineering | Robohelp |
Software Development | Software Reuse |
Structured Design | Testing |
Tools | UML |
Deep Learning with Python by François Chollet(12571)
Hello! Python by Anthony Briggs(9916)
OCA Java SE 8 Programmer I Certification Guide by Mala Gupta(9796)
The Mikado Method by Ola Ellnestam Daniel Brolund(9779)
Dependency Injection in .NET by Mark Seemann(9340)
Algorithms of the Intelligent Web by Haralambos Marmanis;Dmitry Babenko(8299)
Test-Driven iOS Development with Swift 4 by Dominik Hauser(7763)
Grails in Action by Glen Smith Peter Ledbrook(7696)
The Well-Grounded Java Developer by Benjamin J. Evans Martijn Verburg(7557)
Becoming a Dynamics 365 Finance and Supply Chain Solution Architect by Brent Dawson(7082)
Microservices with Go by Alexander Shuiskov(6853)
Practical Design Patterns for Java Developers by Miroslav Wengner(6770)
Test Automation Engineering Handbook by Manikandan Sambamurthy(6709)
Secrets of the JavaScript Ninja by John Resig Bear Bibeault(6416)
Angular Projects - Third Edition by Aristeidis Bampakos(6115)
The Art of Crafting User Stories by The Art of Crafting User Stories(5645)
NetSuite for Consultants - Second Edition by Peter Ries(5577)
Demystifying Cryptography with OpenSSL 3.0 by Alexei Khlebnikov(5381)
Kotlin in Action by Dmitry Jemerov(5065)
